1. Technical Field
The present invention relates to a decoding method, a program for a decoding method, a recording medium with a recorded program for a decoding method, and a decoding device and may be applied to a decoder based on the ITU (International Telecommunication Union)-T H.264 method, for example. The present invention increases the speed of decoding processing compared with that in the related art by detecting continuous numbers of a syntax element of a specific value, such as a value of 0, and decoding the syntax element on the basis of the detection result.
2. Background Art
Conventionally, in coding processing, such as MPEG (Moving Picture Experts Group)-2 and MPEG-4, orthogonal transform processing of image data is performed in a predetermined coding processing unit and variable length coding processing of coefficient data obtained as a result is performed. Furthermore, in the variable length coding processing, variable length coding data is generated with reference to a variable length code table for every code word, which is obtained by combination of the length (run) of continuous coefficients of a value 0 and coefficient values of subsequent coefficient data which is not the value 0, in a coefficient data row obtained in order of zigzag scan.
Regarding the coding processing, Japanese Patent Application Publication No. 2002-76908 proposes a study for increasing the processing speed by processing a run length and a coefficient value which is not a value 0 simultaneously and in parallel.
On the other hand, in CAVLC (Context Adaptive Variable Length Coding) processing based on the ITU-T H.264 method, variable length coding processing of the run number and the coefficient value which is not a value 0 is performed individually. More specifically, in the CAVLC processing based on the ITU-T H.264 method, adaptive variable length coding processing of the coefficient value which is not a value 0 is performed. In addition, one variable length coding table is selected from a plurality of variable length coding tables according to the total number of unprocessed run numbers and coding processing of the run number is performed with the selected variable length coding table.
Here, FIG. 1 is a chart showing syntax elements in CAVLC processing based on the ITU-T H.264 method. Moreover, hereinbelow, regarding each syntax element, for example, a syntax element of TotalCoeff is described as TotalCoeff and description of a syntax element is omitted. In these syntax elements, the TotalCoeff is the number of coefficients (hereinafter, referred to as non-zero coefficients) which exist in a processing block to be encoded and are not the value 0. Therefore, in the case where coefficient data is calculated as shown in FIG. 2A, when a coefficient data row scanned in a zigzag manner from a low order side is shown in FIG. 2B, seven coefficient data of values +23, −4, +11, +8, −3, +1, and −1 are targets of the TotalCoeff. Accordingly, the TotalCoeff becomes a value 7. Furthermore, here, FIG. 2A is a view showing coefficient data obtained by performing orthogonal transform processing of a processing block of 4×4 pixels, in which a number indicates a coefficient value and an arrow indicates zigzag scan from a low order side to a high order side. In addition, FIG. 2B is a table in which the coefficient values of FIG. 2A are arranged in the scan order.
TrailingOnes is the number of coefficients of an absolute value 1 which are continuous at the end of a processing block. In addition, when the number of coefficients of the absolute value 1 is three or more, the TrailingOnes becomes 3. In addition, a coefficient of a value 0 included in the middle is neglected. Therefore, in the example of FIG. 2A, as shown in FIG. 2B, coefficient data of values of +1 and −1 among coefficient data that is continuous in values +1, 0, and −1 is expressed as the TrailingOnes. In this case, the TrailingOnes becomes a value 2.
A coeff token is a syntax element obtained by combining TotalCoeff with TrailingOnes and is expressed as [2, 7] in the example of FIG. 2B.
A trailing ones sign flag denotes signs of coefficients of an absolute value 1 which are continuous at the end. Therefore, targets of the trailing ones sign flag are coefficient values expressed as the TrailingOnes. In the example of FIG. 2B, since coefficient data of values +1 and −1 among the coefficient data which are continuous in +1, 0, and −1 is expressed as the TrailingOnes, signs of the coefficient data of the values +1 and −1 are expressed as the trailing ones sign flag in this case. For the trailing ones sign flag, + and − are expressed as 0 and 1 from a high order side, respectively.
A level prefix is a prefix portion when a coefficient is encoded, and a level suffix is a suffix portion when a coefficient is encoded. A level is a DCT coefficient value, and coefficient data of an absolute value 1 defined as the trailing ones sign flag and coefficient data of a value 0 are excluded.
A total zeros is the total number of zero coefficients and is the number of zero coefficients before a last non-zero coefficient. Accordingly, in the example of FIG. 2, the total zeros becomes a value 5.
A run before is the number of continuous zero coefficients before each non-zero coefficient when a coefficient data row is viewed from the high order side. Therefore, in the example of FIG. 2, since seven coefficient data of values +23, −4, +11, +8, −3, +1, and −1 is non-zero coefficients and the coefficient data of value −1 is a non-zero coefficient located at the head on the high order side, values of the run before become 1, 2, 0, 2, 0, and 0 for coefficient data of values −1, +1, −3, +8, +11, −4, and +23, respectively, as shown in FIG. 2B.
A zerosLeft is the number of unprocessed zero coefficients in total zeros. Therefore, in the example of FIG. 2B, in the case when coefficient data of a value −1 is an object to be processed, the zerosLeft becomes a value 5.
In the CAVLC processing based on the ITU-T H.264 method, each syntax element defined in FIG. 1 is stored in a bit stream in the sequence shown in FIG. 3. Furthermore, here, FIG. 3A shows coefficient data based on orthogonal transform processing, level11 to level0 are coefficient data defined as level, and 0 is coefficient data of a value 0. Furthermore, t1-2 to t1-0 is coefficient data defined as the trailing ones sign flag.
That is, in the bit stream, the coeff token is first assigned and the trailing ones sign flag is subsequently assigned sequentially from the high order side. Furthermore, the level is assigned continuously from the high order side and total zeros are assigned. Furthermore, the run before is assigned continuously from the high order side.
Therefore, in the example of FIG. 2, syntax elements of coeff token [2, 7], trailing ones sign flag −, trailing ones sign flag +, level −3, level +8, level +11, level −4, level +23, total zeros 5, run before 1, run before 2, run before 0, and run before 2 are sequentially stored in a bit stream as shown in FIG. 4. Here, the zerosLeft becomes 0 by processing the run before 2 on a value +8 and processing of run before on coefficient data of a value +11 and a value −4 is not performed.
In the CAVLC processing, corresponding to the storage sequence of syntax elements, processing procedures shown in FIGS. 5 and 6 are executed for every coding processing unit to thereby perform coding processing of each syntax element.
That is, in the coding processing of CAVLC, a movement from step SP1 to step SP2 is made to perform coding processing of the coeff token. Here, in the coding processing, a selection reference value nC of a variable length coding table is calculated from coding processing blocks adjacent to the start end side of raster scan. In addition, the coding processing blocks adjacent to the start end side of raster scan herein are coding processing blocks on immediately above and left sides. Furthermore, the selection reference value nC is an average value of DCT coefficients in the two coding processing blocks, for example. In the coding processing, one variable length coding table is selected from a plurality of variable length coding tables for execution of coding processing of coeff token corresponding to the selection reference value nC, and coding processing of the coeff token is performed based on the selected variable length coding table.
In addition, here, a variable length coding table for execution of coding processing of the coeff token is shown in FIGS. 7 to 10. Five tables in cases where the selection reference value nC is equal to or larger than a value 0 and less than a value 2, the selection reference value nC is equal to or larger than the value 2 and less than a value 4, the selection reference value nC is equal to or larger than the value 4 and less than a value 8, the selection reference value nC is equal to or larger than the value 8, and the selection reference value nC is value −1 are prepared for the coeff token. Therefore, the coeff token [2, 7] in the example of FIG. 2 is encoded to ‘0000 0000 101’, ‘0000 0010 1’, ‘0010 01’, or ‘0110 10’ on the seventh row from above in FIG. 8 corresponding to the selection reference value nC. Accordingly, for example, in the case where the selection reference value nC is equal to or larger than the value 0 and less than the value 2, the coeff token [2, 7] is encoded to ‘0000 0000 101’.
Then, the coding processing moves to step SP3 to check whether or not the total number TotalCoeff of coefficient data is 0. In addition, here, when the total number TotalCoeff of coefficient data is 0, the process moves from step SP3 to step SP4 to complete the processing of the coding block.
On the other hand, when the total number TotalCoeff of coefficient data is not 0, the process moves from step SP3 to step SP5. In step SP5, the coding processing checks that there is no TrailingOnes as a value 0 and the process moves from step SP5 to step SP6.
In step SP6, a value t1s of TrailingOnes is set to a count value n that counts the number of times of processing of trailing ones sign flag. In addition, in subsequent step SP7, a sign of coefficient data (in this case, highest-order coefficient data set as TrailingOnes) specified by the count value n among the coefficient data set as the TrailingOnes is determined and the trailing ones sign flag is set. Furthermore, the count value n is decremented only by the value 1, and in a subsequent step SP8, it is determined whether or not all setting of the trailing ones sign flag has been completed by determination of the count value. Here, when a negative result is obtained, the coding processing returns to step SP7 to set the subsequent trailing ones sign flag. On the other hand, when all setting of the trailing ones sign flag is completed, the process moves from step SP8 to step SP9. In addition, when it is checked that the TrailingOnes is a value 0 in step SP5, the process directly moves from step SP5 to step SP9.
Therefore, in the processing shown in FIG. 5, processing of step SP7 is executed corresponding to the number of trailing ones sign flag. In the example of FIG. 2B, two trailing ones sign flag are encoded to ‘10’.
In subsequent step SP9, the coding processing checks whether or not the value of TotalCoeff does not match the value of TrailingOnes. Here, when it is checked that the value of TotalCoeff does not match the value of TrailingOnes, the coding processing moves to step SP10 in which the value of TrailingOnes is subtracted from the value of TotalCoeff and the number of non-zero coefficients which are not set to trailing ones sign flag is calculated. Furthermore, the calculated value is set to a count value n that counts the number of times of processing of non-zero coefficients.
Subsequently, the coding processing moves to step SP11 and the level of the non-zero coefficient specified by the count value n is context-calculated for coding processing. Furthermore, the count value n is decremented only by the value 1, and in subsequent step SP12, it is determined whether or not all levels of the non-zero coefficients were processed by determination of the count value n. Here, when a negative result is obtained, the coding processing returns to step SP11 to perform coding processing of a level of a subsequent non-zero coefficient. On the other hand, when all levels of the non-zero coefficients are processed, the process moves from step SP12 to step SP13.
In step SP13, it is checked whether or not the TotalCoeff is a maximum value of values which can be taken. Here, when the TotalCoeff is a maximum value of values which can be taken, the process moves from step SP13 to step SP14 to complete the processing procedure since coding processing of all coefficient data has already been completed. On the other hand, when it is checked that the TotalCoeff is not a maximum value of values which can be taken, the process moves from step SP13 to step SP15. In addition, when it is checked that the value of the TotalCoeff matches the value of the TrailingOnes in step SP9, the process directly moves from step SP9 to step SP15.
Therefore, in the coding processing, the levels of non-zero coefficients are decoded by executing the processing in step SP11 as much as a number corresponding to the value of the TotalCoeff. In the example of FIG. 2B, levels of −3, +8, +11, −4, and +23 are sequentially processed to generate a coded data row of ‘0001 0000 0001 0000 0010 0111 1000 0011 00’.
In subsequent step SP15, coding processing performs coding processing of total zeros using a coding table. Here, variable length coding tables for execution of coding processing of total zeros prepared in the coding processing unit of 4×4 blocks and 2×2 blocks are shown in FIGS. 11 and 12, respectively. In the total zeros, a table is prepared corresponding to each value of TotalCoeff. Accordingly, the coding processing selects a table according to the value of TotalCoeff and performs coding processing of the total zeros using the selected table. Therefore, the value 5 of total zeros in the example of FIG. 2B is encoded to ‘11’ since the TotalCoeff is a value 7.
In addition, subsequently, the value of total zeros is set to an initial value of zerosLeft. In addition, the value of TotalCoeff is set to the count value n which counts the number of times of processing of zerosLeft. Then, the process moves to step SP16 to check whether or not the value of total zeros is 0. When the value of total zeros is 0, the process moves from step SP16 to step SP14 to complete the processing procedure. On the other hand, when the value of total zeros is not 0, the process moves from step SP16 to step SP17.
In this step SP17, in the coding processing, coding processing of run before of a non-zero coefficient (in this case, a non-zero coefficient on the highest-order side) specified by the count value n indicating the number of times of processing is performed to update the zerosLeft and the count value n. In addition, in subsequent step SP18, the zerosLeft is determined to determine whether or not there is unprocessed run before. When a negative result is obtained herein, the process moves from step SP18 to step SP14 to complete the processing procedure. On the other hand, when a positive result is obtained in step SP18, the process moves from step SP18 to step SP19 to determine whether or not there is run before of unprocessed coefficient processing by determination of the count value n. When a negative result is obtained herein, the process moves from step SP19 to step SP14 to complete the processing procedure. On the other hand, when a positive result is obtained in step SP19, the process moves from step SP19 to step SP17 to continuously perform coding processing of run before.
Here, FIG. 13 is a flow chart showing processing procedures of coding processing of syntax elements of run before. In addition, the processing procedures of FIG. 13 show the processing procedures of steps SP17-SP18-SP19-SP17 of FIG. 6 in detail. Accordingly, it is needless to say that some of the following description overlaps descriptions of FIGS. 5 and 6.
When the processing procedures start, the coding processing moves from step SP31 to step SP32 to set TotalCoeff to the count value n indicating the number of times of processing. In addition, total zeros are set to an initial value of zerosLeft which is the number of unprocessed zero coefficients.
In addition, in subsequent step SP33, a table which performs coding processing of the run before with the value of zerosLeft is selected. Here, a table which performs coding processing of the run before is shown in FIG. 14. Seven tables in cases where the value of zerosLeft which is the number of unprocessed zero coefficients is a value 1, the value of zerosLeft is a value 2, the value of zerosLeft is a value 3, the value of zerosLeft is a value 4, the value of zerosLeft is a value 5, the value of zerosLeft is a value 6, and the value of zerosLeft is larger than a value 6 are prepared for the run before, and a table used for coding processing is selected according to the value of zerosLeft. Here, in the case of FIG. 2B, the total zeros are 5. Accordingly, in this case, a table in which the total zeros are the value 5 is selected.
Then, the coding processing moves to step SP34 in which coding processing of the run before specified by the count value n is performed by using the table selected in step SP33. Therefore, in the example of FIG. 2B, the run before of a value 1 which is the number of continuous zero coefficients immediately before a coefficient of −1, which is located at the fifth coefficient from the high order side, is encoded to ‘10’.
Then, the CAVLC processing moves to step SP35 in which the value of run before encoded in the last step SP34 is subtracted from the value of zerosLeft and the value of zerosLeft which is the number of unprocessed zero coefficients is updated. In addition, a value 1 is subtracted from the count value n indicating the number of times of processing.
Then, in the CAVLC processing, it is determined whether or not coding processing of all the run before has been completed by determination of the value of zerosLeft. When a positive result is obtained herein, the process moves to step SP37 to complete the processing procedure. On the other hand, when a negative result is obtained in step SP36, the process moves from step SP36 to step SP38.
Then, in the CAVLC processing, it is determined whether or not coding processing of all the run before has been completed by determination of the count value n indicating the number of times of processing. When a positive result is obtained herein, the process moves to step SP37 to complete the processing procedure. On the other hand, when a negative result is obtained in step SP38, the process moves from step SP38 to step SP40. Then, in step SP40, a table which performs coding processing of the run before with the value of zerosLeft is selected, and the process moves to step SP34.
Therefore, in the example of FIG. 2B, in the processing of step SP34, a table in the case where the value of zerosLeft is 4 is selected and the run before of a value 2 which is the number of continuous zero coefficients immediately before a coefficient of +1, which is located at the seventh coefficient from the high order side, is encoded to ‘01’ using the table. In addition, in subsequent step SP35, the value of zerosLeft is updated to the value 2 and then the process moves from steps SP36 and SP38 to step SP40. Here, the zerosLeft selects the table of the value 2. Furthermore, coding processing of the run before value 0 is performed for a coefficient of −3 located at the tenth coefficient from the high order side by using the table. In addition, by repeating the same processing, the value 2 of run before of coefficient data of the subsequent value +8 is encoded to ‘00’ using the table of the value 2 of zerosLeft, and the coding processing of run before is completed.
By processing of FIGS. 5, 6, and 13, a bit stream of ‘0000 0000 1011 0000 1000 0000 1000 0001 0011 1100 0001 1001 1100 1100’ is generated in the example shown FIG. 2B. In addition, FIG. 15 is a chart showing coding processing with the case of FIG. 2B as an example.
On the other hand, at the time of decoding, a bit stream is processed sequentially in the same sequence as in encoding, syntax is sequentially decoded and each of coefficient data is decoded by using the decoded syntax. Furthermore, the decoding is executed in the same manner as the coding processing by sequentially executing the processing procedures of FIGS. 5 and 6 except that a table searching method and a context processing method are executed corresponding to decoding processing. Therefore, the processing at the time of decoding will be described using FIGS. 5 and 6. In addition, FIG. 16 is a chart showing a series of processing in a case where decoding processing of an input bit stream of ‘0000 0000 1011 0000 1000 0000 1000 0001 0011 1100 0001 1001 1100 1100’ is performed in the example of FIG. 2.
In this case, in the decoding processing, the table selected at the time of coding is selected from the tables shown in FIGS. 7 to 10 by calculating the selection reference value nC and 11-bit ‘0000 0000 101’ on the head side of the input bit stream is decoded to coeff token [2, 7] by pattern matching using the table (FIG. 5, step SP2). In addition, the input bit stream is bit-shifted by the 11 bits on the head side.
In addition, subsequently, it is detected that TrailingOnes is a value 2 from the decoding result of coeff token [2, 7], and the next two bits ‘10’ are decoded to trailing ones sign flag − and + on the basis of the detection result (FIG. 5, step SP7). In addition, the input bit stream is bit-shifted by the 2 bits.
Then, it is detected that TotalCoeff is a value 7 from the decoding result of coeff token [2, 7], and context calculation of levels of coefficients of five coefficients 0 is performed for decoding processing since TrailingOnes is a value 2 (FIG. 6, step SP11). Then, by bit-shifting the input bit stream by the decoded level, a bit stream of ‘1 1100 1100’ remains in the example of FIG. 2.
Subsequently, in the decoding processing, a table (FIGS. 11 and 12) in which the TotalCoeff is a value 7 is selected, pattern matching processing of the remaining bit stream is performed, and the front two bits ‘11’ of the remaining input bit stream are decoded to the value 5 of total zeros (FIG. 6, step SP15). In addition, the input bit stream is set to ‘100 1100’ by bit-shifting the remaining input bit stream ‘1 1100 1100’ by the 2 bits.
Then, in the decoding processing, the run before is decoded by sequentially processing the remaining input bit stream ‘100 1100’.
Here, FIG. 17 is a flow chart showing decoding procedures of run before by comparison with FIG. 13. When the processing procedures start, the decoding processing moves from step SP41 to step SP42 to set TotalCoeff to the count value n indicating the number of times of processing. In addition, total zeros are set to an initial value of zerosLeft which is the number of unprocessed zero coefficients.
In addition, in subsequent step SP43, a table which performs decoding processing of the run before with the value of zerosLeft is selected. Then, the decoding processing proceeds to step SP44 in which decoding processing of the run before specified by the count value n is performed by using the table selected in step SP43. Therefore, in the example of FIG. 2B, for a coefficient of −1 which is located at the fifth coefficient from the high order side, the front two bits ‘10’ of the remaining input bit stream ‘100 1100’ is decoded to the value 1 of run before. In addition, the input bit stream is set to ‘0 1100’ by bit-shifting the remaining input bit stream ‘100 1100’ by the 2 bits.
Then, the decoding processing proceeds to step SP45 in which the value of run before decoded in the last step SP44 is subtracted from the value of zerosLeft and the value of zerosLeft which is the number of unprocessed zero coefficients is updated. In addition, a value 1 is subtracted from the count value n indicating the number of times of processing.
Then, in the decoding processing, it is determined whether or not decoding processing of all the run before has been completed by determination of the value of zerosLeft. When a positive result is obtained herein, the process moves to step SP47 to complete the processing procedure. On the other hand, when a negative result is obtained in step SP46, the process moves from step SP46 to step SP48.
Then, in the decoding processing, it is determined whether or not decoding processing of all the run before has been completed by determination of the count value n indicating the number of times of processing. When a positive result is obtained herein, the process moves to step SP47 to complete the processing procedure. On the other hand, when a negative result is obtained in step SP48, the process moves from step SP48 to step SP49. Then, in step SP49, a table which performs coding processing of the run before with the value of zerosLeft is selected, and the process moves to step SP44.
Therefore, in the example of FIG. 2B, in the processing of step SP44, a table in the case where the value of zerosLeft is 4 is selected and the front two bits ‘01’ of the remaining input bit stream ‘0 1100’ is decoded to the value 2 of run before for a coefficient of +1, which is located at the seventh coefficient from the high order side, by pattern matching processing using the table. In addition, the input bit stream is set to ‘100’ by bit-shifting the remaining input bit stream ‘0 1100’ by the 2 bits.
In addition, in subsequent step SP45, the value of zerosLeft is updated to the value 2 and then the process moves from steps SP46 and SP48 to step SP44. Here, the zerosLeft selects the table of the value 2. In addition, by pattern matching processing using the table, the front one bit ‘1’ of the remaining input bit stream ‘100’ is decoded to the value 0 of run before for a coefficient of −3 which is located at the tenth coefficient from the high order side. In addition, the input bit stream is set to ‘00’ by bit-shifting the remaining input bit stream ‘100’ by the 1 bit. In addition, by repeating the same processing, a table in which the zerosLeft is a value 2 is selected and is subjected to pattern matching processing for coefficient data of the subsequent value +8, and the front two bits ‘00’ of the remaining input bit stream ‘00’ is decoded to the value 2 of run before. Subsequently, the value of zerosLeft is updated to the value 0 in step SP45 and the positive result is obtained in step SP46, completing the decoding processing.
However, in the decoding processing described above, a table is selected on the basis of the last processing result to decode a specific syntax element. Specifically, in case of decoding the run before, a variable length table used in the decoding changes with the total number of unprocessed run numbers, such that the total number of unprocessed run numbers is decided by decoding of the last run before. Therefore, in the decoding processing of run before, it is necessary to sequentially process the continuous run before. After all, there was a problem that the speed of the decoding processing could not be increased.